#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int change(int amount, vector<int>& coins)
    {
        vector<long> dp(amount + 1);
        dp[0] = 1;
        for (auto x : coins)
            for (long j = x; j <= amount; j++)
                dp[j] += dp[j - x];

        return dp[amount];
    }
};